package com.shuzijun.leetcode.editor.cn;
public class TargetSum{
    public static void main(String[] args) {
         Solution solution = new TargetSum().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if (S > 1000 || S < -1000) return 0;
        int n = nums.length;
        int offset = 1000;
        int w = 2000;
        int[][] dp = new int[n][w + 1];
        dp[0][offset-nums[0]] += 1;
        dp[0][offset+nums[0]] += 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (j-nums[i]>=0 && j-nums[i] <= w){
                    dp[i][j] = dp[i-1][j-nums[i]];
                }
                if (j+nums[i]>=0 && j+nums[i] <= w){
                    dp[i][j] += dp[i-1][j+nums[i]];
                }
            }
        }
        return dp[n-1][S+1000];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}